package com.llb666.java.leetcode.tree;

import java.util.ArrayList;
import java.util.Stack;

/**
 * Created by 斌~
 * 2021/5/18 17:44
 *                         1
 *                  2             3
 *              4      5
 *                 6       7
 */
public class 二叉树遍历 {
    public static void main(String[] args) {
        TreeNode node7 = new TreeNode(7, null, null);
        TreeNode node6 = new TreeNode(6, null, null);
        TreeNode node5 = new TreeNode(5, node6, node7);
        TreeNode node4 = new TreeNode(4, null, null);
        TreeNode node3 = new TreeNode(3, null, null);
        TreeNode node2 = new TreeNode(2, node4, node5);
        TreeNode node1 = new TreeNode(1, node2, node3);

//        perOrder(node1);  //前序遍历-递归 1 2 4 5 6 7 3
//        midOrder(node1);  //中序遍历-递归 4 2 6 5 7 1 3
//        nextOrder(node1); //后序遍历-递归 4 6 7 5 2 3 1

        //层次序遍历 1 2 3 4 5 6 7
//        ArrayList<Integer> list =new ArrayList<>();
//        levelOrder(node1,1,list);
//        Arrays.stream(list.toArray()).filter(Objects::nonNull).forEach(System.out::println);

//        perOrder2(node1);  //前序遍历-递归 1 2 4 5 6 7 3
//        midOrder2(node1);  //中序遍历-递归 4 2 6 5 7 1 3
        nextOrder2(node1); //后序遍历-递归 4 6 7 5 2 3 1

    }



    /**
     * ----------------------层序遍历-------------递归实现
     * @param root 根节点
     */
    private static void levelOrder(TreeNode root,int i, ArrayList<Integer> list) {
        if(root == null){
            return;
        }
        int length = list.size();
        if (length <= i){
            for (int j = 0; j <= i-length; j++) {
                list.add(length +j,null);
            }
        }
        list.set(i,root.val);
        levelOrder(root.left,2*i,list);
        levelOrder(root.right,2*i+1,list);
    }

    /**
     * ----------------------前序遍历-------------递归实现
     * @param root 根节点
     */
    private static void perOrder(TreeNode root) {
        if(root ==null){
            //节点为空，出栈
            return;
        }
        //第一次成为栈顶元素就打印
        System.out.println(root.val);
        perOrder(root.left);
        perOrder(root.right);
    }

    /**
     * -----------------------中序遍历-------------递归实现，找到最左边的才开始打印，
     * @param root 根节点
     */
    private static void midOrder(TreeNode root) {
        if(root ==null){
            //节点为空，出栈
            return;
        }
        midOrder(root.left);
        //第二次成为栈顶元素才开始打印
        System.out.println(root.val);
        midOrder(root.right);
    }

    /**
     * -------------------------后序遍历-------------递归实现
     * @param root 根节点
     */
    private static void nextOrder(TreeNode root) {
        if(root ==null){
            //节点为空，出栈
            return;
        }
        nextOrder(root.left);
        nextOrder(root.right);
        //第三次成为栈顶元素才开始打印
        System.out.println(root.val);
    }



/**
 *  -----------------------二叉树实体类---------------------------
 */
    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        int deep;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }

        private TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    /**
     * ----------------------前序遍历-------------栈实现
     * @param root 根节点
     */
    private static void perOrder2(TreeNode root) {
        if(root !=null){
            Stack<TreeNode> stack = new Stack<>();
            stack.add(root);
            while(!stack.isEmpty()){
                //获取栈顶元素
                root = stack.pop();
                if(root != null){
                    System.out.println(root.val);
                    //放入栈顶，因为前序遍历需要先打印'左节点'，所以'右节点'先放入栈中
                    stack.push(root.right);
                    stack.push(root.left);
                }
            }
        }
    }


    /**
     * ----------------------中序遍历-------------栈实现，左根右
     * @param root 根节点
     */
    private static void midOrder2(TreeNode root) {
        if(root !=null){
            Stack<TreeNode> stack = new Stack<>();
            while(!stack.isEmpty() || root !=null){
                if (root !=null){
                    stack.push(root);
                    root = root.left;
                }else {
                    root = stack.pop();
                    System.out.println(root.val);
                    root = root.right;
                }
            }
        }
    }

    /**
     * ----------------------后序遍历-------------栈实现，左右根
     * @param root 根节点
     */
    private static void nextOrder2(TreeNode root) {
        if(root !=null){
            Stack<TreeNode> stack = new Stack<>();
            TreeNode prev = null;
            while(!stack.isEmpty() || root !=null){
                while (root !=null){
                    stack.push(root);
                    root = root.left;
                }
                root = stack.pop();
                if(root.right == null || root.right ==prev){
                    System.out.println(root.val);
                    prev = root;
                    root = null;
                }else {
                    stack.push(root);
                    root = root.right;
                }
            }
        }
    }
}


